/*
 * @lc app=leetcode id=19 lang=cpp
 *
 * [19] Remove Nth Node From End of List
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    int getLen(ListNode *head) {
        int len = 0;
        ListNode *node = head;
        while(node) {
            node = node->next;
            len++;
        }
        return len;
    }
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        if (n < 1 || !head) {
            return head;
        }

        int len = getLen(head), gap = len-n;
        if (len < n) {
            return head;
        }

        ListNode *node = head, *tmp = NULL;
        if (gap == 0) {
            head = node->next;
            delete node;
        } else {
            while(node && --gap > 0) {
                node = node->next;
            }
            tmp = node->next;
            node->next = tmp->next;
            delete tmp;
        }

        return head;
    }
};

